#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#define maxn 1000
using namespace std;
vector<int> arr;
void qsort(vector<int> &arr, int l, int r)
{
    if (l >= r)
        return;
    swap(arr[(l + r) / 2], arr[r]);
    int i = l - 1, pivot = arr[r];
    for (int j = l; j < r; ++j)
    {
        if (arr[j] < pivot)
        {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[r]);
    qsort(arr, l, i);
    qsort(arr, i + 2, r);
}
void show(vector<int> &arr)
{
    for (auto &it : arr)
        printf(" %d", it);
    printf("\n");
};
int main()
{
    arr = {2, 3, 1, 3, 4, 2, 3, 4, 5, 6, 7, 84, 3, 2, 3};
    show(arr);
    qsort(arr, 0, arr.size() - 1);
    show(arr);

    return 0;
};